Search results for "Molecular computing"

showing 3 items of 3 documents

On the regularity of circular splicing languages : A survey and new developments

2009

Circular splicing has been introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we focus on the relationship between regular circular languages and languages generated by finite circular splicing systems. We survey the known results towards a characterization of the intersection between these two classes and provide new contributions on the open problem of finding this characterization. First, we exhibit a non-regular circular language generated by a circular simple system thus disproving a known result in this area. Then we give new results related to a restrictive class of circular splicing systems…

Discrete mathematicsComputer scienceOpen problemINF/01 - INFORMATICAGraph theoryCircular wordMolecular computingComputer Science ApplicationsGraph theoryAutomata theory Circular words Formal languages Graph theory Molecular computing Splicing systemsIntersectionFormal languageTheory of computationGraph (abstract data type)CographFormal languageSplicing systemComplement (set theory)Automata theory
researchProduct

Marked systems and circular splicing

2007

Splicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. In this paper we introduce a special class of finite circular splicing systems named marked systems. We prove that a marked system S generates a regular circular language if and only if S satisfies a special (decidable) property. As a consequence, we show that we can decide whether a regular circular language is generated by a marked system and we characterize the structure of these regular circular languages.

Discrete mathematicsProperty (programming)Structure (category theory)Molecular computingCircular wordDecidabilityRegular languageIf and only ifRNA splicingFormal languageSplicing systemFormal languageGenerative grammarAutomata theoryMathematics
researchProduct

A characterization of regular circular languages generated by marked splicing systems

2009

AbstractSplicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. A splicing system is defined by giving an initial set I and a set R of rules. Some unanswered questions are related to the computational power of circular splicing systems. In particular, a still open question is to find a characterization of circular languages generated by finite circular splicing systems (i.e., circular splicing systems with both I and R finite sets). In this paper we introduce a special class of the latter systems named marked systems. We prove that a marked system S generates a regular circular language if an…

Pure mathematicsGeneral Computer ScienceMolecular computing Splicing systems Circular words Formal languages Automata theoryMolecular computingQuantitative Biology::GenomicsDecidabilityTheoretical Computer ScienceSet (abstract data type)Formal languagesRegular languageFormal languageRNA splicingAutomata theorySplicing systemsCircular wordsFinite setAlgorithmWord (computer architecture)Automata theoryMathematicsComputer Science(all)
researchProduct